package com.example.algorithm.dynamicprogramming;

/**
 * 这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
 *  给定三个整数 n , k 和 target ，返回可能的方式(从总共 kⁿ 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。
 *  答案可能很大，你需要对 10⁹ + 7 取模 。
 *
 *  示例 1：
 * 输入：n = 1, k = 6, target = 3
 * 输出：1
 * 解释：你扔一个有6张脸的骰子。
 * 得到3的和只有一种方法。
 *
 *  示例 2：
 * 输入：n = 2, k = 6, target = 7
 * 输出：6
 * 解释：你扔两个骰子，每个骰子有6个面。
 * 得到7的和有6种方法1+6 2+5 3+4 4+3 5+2 6+1。
 *
 *  示例 3：
 * 输入：n = 30, k = 30, target = 500
 * 输出：222616187
 * 解释：返回的结果必须是对 10⁹ + 7 取模。
 */
public class Leetcode1155_NumRollsToTarget {
    static class Solution {
        /**
         * 动态规划
         * 相当于从一个数组[1, 2, 3..., k]有放回的取 n 个数，求能是的取出和为 target 的取法(要看顺序)
         * dp[i][j] 表示前i个骰子能够得到的结果和为 j 的排列数
         * 要 i 个骰子的和为j ， 设 第 i 个骰子的点数为diceNum, 则前 i - 1 个骰子的和必为 j - diceNum
         * 即： dp[i][j] = sum(dp[i - 1, j - diceNum]) 其中 1 <= diceNum <= k
         * @param n
         * @param k
         * @param target
         * @return
         */
        public int numRollsToTarget(int n, int k, int target) {
            final int MOD = (int) Math.pow(10, 9) + 7;
            int[][] dp = new int[n + 1][target + 1]; // dp[i][j] = m 表示前i个骰子能够得到的结果和为 j 的排列数为 m
            dp[0][0] = 1;
            for (int i = 1; i <= n; i++) { // 一共有 n 个骰子
                for (int diceNum = 1; diceNum <= k; diceNum++) { // 每个骰子取值可能有 1-k(对骰子的所有可能值进行遍历)
                    for (int j = diceNum; j <= target; j++) { // 求 i 个骰子能组成和为 j 的总组合数
                        dp[i][j] = (dp[i][j] + dp[i - 1][j - diceNum]) % MOD;
                    }
                }
            }
            return dp[n][target] % MOD;
        }
    }

    public static void main(String[] args) {
        int n = 2, k = 6, target = 7;
        n = 30; k = 30; target = 500;
        System.out.println(new Solution().numRollsToTarget(n, k, target));
    }
}
